/**
 * 
 */
package leetCode;

/**
 * 根节点比所有节点大，从数组中构造树：找到最大的，作为根节点，它的左边是左子树，右边是右子树
 * 
 * 给定A数组构造成的树以及增加在末尾的一个数值，求构造成的新的树.ps:保证所有数值不同
 * 
 * 思考：因为旧的树已经有序，所以只需要在旧的树上面增加东西即可，如果这个数比当前节点大，则设置这个数的左子为当前节点，且父节点指向新节点；如果小于，则沿着树的右子走。特殊情况：原来的树为空，直接返回新节点。
 * 
 * @author zhong
 *
 */
public class MaximumBinaryTreeII {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public TreeNode insertIntoMaxTree(TreeNode root, int val) {
		if (root == null) {
			return new TreeNode(val);
		}
		if (root.val < val) {
			TreeNode cur = new TreeNode(val);
			cur.left = root;
			return cur;
		}
		TreeNode newChild = insertIntoMaxTree(root.right, val);
		root.right = newChild;
		return root;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
